package com.longge;

public class NumRollsToTarget {
    static final int MOD = 1000000007;


    public int numRollsToTarget(int n, int k, int target) {

        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                for (int x = 1; x <= k; x++) {
                    if (j - x >= 0) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - x])%MOD;
                    }
                }
            }

        }
        return dp[n][target];
    }

    public static void main(String[] args) {
        int i = new NumRollsToTarget().numRollsToTarget(1, 6, 3);
        System.out.println(i);
    }
}
